// 给一个有序数组查看有没有重复值，要求算法复杂度O（n） 空间复杂度不能为O（n）

//arr.sort O(n log n)的时间复杂度和O(1)的额外空间复杂度（不考虑输入数组本身所占用的空间）

function hasDuplicate(arr) {
    // 首先对数组进行排序 有序数组的话不用做这一步
    arr.sort((a, b) => a - b);
    // 然后检查相邻元素是否相同
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] === arr[i - 1]) {
            return true;
        }
    }
    return false;
}

// 示例
console.log(hasDuplicate([1, 2, 3, 4, 5])); // false
console.log(hasDuplicate([1, 2, 3, 4, 4])); // true